//Given the root of a binary search tree (BST) with duplicates, return all the 
//mode(s) (i.e., the most frequently occurred element) in it. 
//
// If the tree has more than one mode, return them in any order. 
//
// Assume a BST is defined as follows: 
//
// 
// The left subtree of a node contains only nodes with keys less than or equal 
//to the node's key. 
// The right subtree of a node contains only nodes with keys greater than or 
//equal to the node's key. 
// Both the left and right subtrees must also be binary search trees. 
// 
//
// 
// Example 1: 
// 
// 
//Input: root = [1,null,2,2]
//Output: [2]
// 
//
// Example 2: 
//
// 
//Input: root = [0]
//Output: [0]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the tree is in the range [1, 10⁴]. 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//Follow up: Could you do that without using any extra space? (Assume that the 
//implicit stack space incurred due to recursion does not count).
//
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 787 👎 0

package leetcode.editor.cn;

import java.util.*;
import java.util.function.BiFunction;

class P501FindModeInBinarySearchTree{
    //2025-02-12 22:56:40
    //Find Mode in Binary Search Tree
    //编号：[501]
    
    public static void main(String[] args) {
    
        Solution solution = new  P501FindModeInBinarySearchTree().new Solution();
        int[] mode = solution.findMode(new TreeNode(0));
        System.out.printf("");
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> path = new HashMap<>();
        traverse(root, path);
        List<Integer> sort = new ArrayList<>();
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : path.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            if (value == count) {
                sort.add(key);
            } else if (value > count) {
                count = value;
                sort.clear();
                sort.add(key);
            }
        }
        int[] result = new int[sort.size()];
        for (int i = 0; i < sort.size(); i++) {
            result[i] = sort.get(i);
        }
        return result;
    }

    public void traverse(TreeNode root, Map<Integer,Integer> path) {
        if (root == null) {
            return;
        }
        traverse(root.left,path);
        path.compute(root.val, (key, oldValue) -> {
            if (oldValue == null) {
                return 1;
            }
            return oldValue + 1;
        });
        traverse(root.right,path);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}